1. Field of the Invention
This invention relates to the field of digital communications, and more specifically to authentication of binary coded communications.
2. Description of the Prior Art
Vast quantities of information are routinely transmitted from one place to another by means which allow a message to be intercepted by unauthorized persons. In many cases serious harm could result if such persons were able to transmit their own improper messages in place of an authorized one, or to transmit previously intercepted proper messages at an improper time. Examples of communication systems where harm could occur from such unauthorized transmissions include funds transfer and accounting messages between financial institutions and command and control information for satellites. There is a need for means which allow the receiver of a message to be assured that the message has been correctly received and that it was transmitted from an authorized source.
A method well known in the prior art for insuring that a message has been received without errors is by use of cyclic error correcting codes generated by feedback registers. A substantial amount of literature is available on such codes; for example, see W. Wesley Peterson, Error-Correcting Codes, MIT, 1961. A particular type of cyclic code generator described therein is known as a Galois register. FIG. 1 illustrates such an apparatus with an 8-stage binary shift register S divided by a first mod-2 adder 10 between the third and fourth stages S.sub.3 and S.sub.4 respectively, and a mod-2 adder 11 between the fifth and sixth stages. A third mod-2 adder 12 sums the contents of S.sub.8 and an external input I.sub.1, with the sum provided as an input to S.sub.1. Following an initial preset step where the stages are loaded with some sequence of binary digits, the contents of each stage of the register at a given time t is a known function of the register contents at time t-1, one clock pulse earlier and the external input I.sub.1.sup.t. Specifically with reference to FIG. 1, the contents of stage 6 at time t is equal to the contents of stage 8 at time t-1 plus the contents of stage 5 at t-1, or EQU S.sub.6.sup.t =S.sub.8.sup.t-l .sym.S.sub.5.sup.t-1
where .sym. indicates mod-2 addition.
Similarly, EQU S.sub.8.sup.t =S.sub.7.sup.t-1 EQU S.sub.7.sup.t =S.sub.6.sup.t-1 EQU S.sub.5.sup.t =S.sub.4.sup.t-1 EQU S.sub.4.sup.t =S.sub.8.sup.t-1 .sym.S.sub.3.sup.t-1 EQU S.sub.3.sup.t =S.sub.2.sup.t-1 EQU S.sub.2.sup.t =S.sub.1.sup.t-1 EQU S.sub.1.sup.t =S.sub.8.sup.t-1 .sym.I.sub.l.sup.t.
FIG. 2 illustrates a similar apparatus with an 8-stage register T broken by a first mod-2 adder 20 between stages T.sub.2 and T.sub.3, a second mod-2 adder 21 between stages T.sub.6 and T.sub.7, and a third mod-2 adder 22 providing the sum of T.sub.8 and to T.sub.1. This register steps according to the rules EQU T.sub.8.sup.t =T.sub.7.sup.t-1 EQU T.sub.7.sup.t =T.sub.8.sup.t-1 .sym.T.sub.6.sup.t-1 EQU T.sub.6.sup.t =T.sub.5.sup.t-1 EQU T.sub.5.sup.t =T.sub.4.sup.t-1 EQU T.sub.4.sup.t =T.sub.3.sup.t-1 EQU T.sub.3.sup.t =T.sub.8.sup.t-1 .sym.T.sub.2.sup.t-1 EQU T.sub.2.sup.t =T.sub.1.sup.t-1 EQU T.sub.1.sup.t =T.sub.8.sup.t-1 .sym.I.sub.2.sup.t.
The manner in which Galois registers are used for error detecting is well known, and will not be discussed here. Details are available in the above-identified reference by Peterson.